/*
ID:luongho3
LANG:C++
TASK:inflate
*/
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("inflate.in");
ofstream fout("inflate.out");
#define SIZE 10001
int t_max, n_class;
int tim[SIZE], point[SIZE];
int best[SIZE];
int main() {
    int i,j;
    fin >> t_max >> n_class;
    for (i=1;i<=n_class;++i) {
        fin >> point[i] >> tim[i];
    }
    for (i=0;i<=t_max;++i) {
        best[i] = (i / tim[1]) * point[1];
    }
    for (j=2;j<=n_class;++j) {
        for (i=0;i<=t_max;++i) {
            if (i >= tim[j]) {
                  best[i] = best[i] > best[i-tim[j]] + point[j] ? best[i] : best[i-tim[j]] + point[j];
            }
        }
    }
    fout << best[t_max] <<"\n";
    return 0;
}
